package app_demo;

import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicReferenceArray;

/**
 * @Description 实现一个线程安全的循环队列
 * @Author Firenut
 * @Date 2023-07-30 15:48
 */
public class MyCircularQueue {
    private AtomicReferenceArray<Integer> queue;
    private AtomicInteger front, rear;

    public MyCircularQueue(int k) {
        queue = new AtomicReferenceArray<>(k + 1);
        front = rear = new AtomicInteger(0);
    }

    public boolean enQueue(int value) {
        // 如果队列满了，不能加入
        if (isFull()) {
            return false;
        }

        // 如果队列为空
        int nexIndex = rear.get();
        while (!queue.compareAndSet(nexIndex, null, value)) {
            // 如果其他线程进行了修改导致队列满了，就不再重试了
            if(isFull()) return false;
            nexIndex = rear.get();
        }

        // 更新rear指针
        int currentTail = rear.get();
        while (!rear.compareAndSet(currentTail, (currentTail + 1) % queue.length())) {
            currentTail = rear.get();
        }
        return true;
    }

    // 队头出队
    public boolean deQueue() {
        if (isEmpty()) return false;
        int currentHead = front.get();
        Integer headElement = queue.get(currentHead);
        // 尝试将队头元素设置为null,必须设置为null，不然后面就没法判断这个位置是否是空闲的空间
        while (!queue.compareAndSet(currentHead, headElement, null)) {
            currentHead = front.get();
            headElement = queue.get(currentHead);
        }
        // 修改front的下标
        currentHead = front.get();
        while (!front.compareAndSet(currentHead, (currentHead + 1) % queue.length())) {
            currentHead = front.get();
        }
        return true;
    }

    public int Front() {
        return isEmpty() ? -1 : queue.get(front.get());
    }

    public int Rear() {
        // 这里rear-1可能会等于-1，所以还需要加上 queue.length
        return isEmpty() ? -1 : queue.get((rear.get() - 1 + queue.length()) % queue.length());
    }

    public boolean isEmpty() {
        return front.equals(rear);
    }

    public boolean isFull() {
        return (rear.get() + 1) % queue.length() == front.get();
    }
}
